//
// Created by BWY on 2024/2/13.
// 折半查找
#include <vector>

using namespace std;
// 折半查找非递归算法
int BinSearch1(vector<int>& R,int k) {
    int n = R.size();
    int low = 0, high = n - 1;
    while(low <= high)      // 当前区间非空时
    {
        int mid = low + (high - low) / 2;   // 求查找区间的中间位置
        if(k == R[mid])                     // 查找成功则返回其序号mid
            return mid;
        if(k < R[mid])
            high = mid - 1;         // 继续在R[low..mid-1]中查找
        else
            low = mid + 1;          // 继续在R[mid+1..high]中查找
    }
    return -1;                      // 当前查找区间空时返回-1
}

// 被BinSearch2方法调用
int BinSearch2(vector<int>& R, int low, int high, int k)
{
    if(low > high)      // 当前查找区间空时返回-1
        return -1;

    int mid = low + (high - low) / 2;
    if(k == R[mid])    // 查找成功则返回其序号mid
        return mid;
    if(k < R[mid])  // 递归在左区间查找
        return BinSearch2(R,low,mid-1,k);
    else            // 递归在右区间查找
        return BinSearch2(R,mid+1,high,k);
}
// 折半查找递归算法
int BinSearch2(vector<int>& R, int k) {
    return BinSearch2(R,0,R.size()-1,k);
}
